package ro;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.ListIterator;

public class UFind {
	
	private int pere[];

        /**
         * 
         * @param taille Edge number of the considered graph
         */
	public UFind(int taille){
		pere = new int[taille];
		
		for(int i = 0 ; i < taille ; i++){
			pere[i]=-1;
		}
	}

        /**
         *
         * @param element Searches the root of element's tree
         * @return The index of element's tree root
         */
	public int find(int element){
		int papa=pere[element]; //la racine
		int pere_adoptif; //le pere du noeud courant
		
		if (papa < 0)
			return element;
		//On parcourt l'arbre pour trouver la racine on la stocke dans papa
		while(pere[papa] >= 0){
			papa = pere[papa];
		}
		//On va mettre la racine comme pere de tous les elements de la composants connexe		
		while(pere[element]!=papa){
			pere_adoptif = pere[element];
			pere[element] = papa;
			element = pere_adoptif;
		}
		return papa;
	}

        /**
         *
         * @param e1 an element of a tree
         * @param e2 an element of a tree
         * @return True if e1's tree and e2's tree has been joined, false if they hasn't ( if e1 and e2 already were in the same tree )
         */
	public boolean union(int e1, int e2){
		//rt1 et rt2 sont les racines des arbres dont e1 et e2 sont des éléments
		int rt1 = find(e1);
		int rt2 = find(e2);
		
		if(rt1==rt2)
			return false;
		//Si le poids de rt1 est supérieur à celui de rt2 (ce sont des négatifs)
		if (pere[rt1] < pere[rt2]){
			//rt1 devient le père de rt2
			pere[rt2]=rt1;
		}
		//Si ils ont le même poids
		else if (pere[rt1] == pere[rt2]){
				pere[rt2]=rt1; //rt1 devient le père de rt2
				pere[rt1]--; //On augmente le poids (toujours des négatifs)
		}
		else{
			//rt2 devient le père de rt1
			pere[rt1]=rt2;
		}
		return true;
		
	}


	public int[] getPeres(){
		return pere;
	}

        /**
         *
         * @param g The graph from which we want to exctract the MST
         * @return The list of 
         */
	public ArrayList<Edge> kruskal(Graph g){
		ArrayList<Edge> aretes = new ArrayList<Edge>();
		aretes = g.getArete();
		ArrayList<Edge> tmp = new ArrayList<Edge>();
		
		if(aretes == null){
			
			System.exit(0);
		}
		
		else{
			Edge.triRapide(aretes);
			for(Edge e : aretes){
				if(union(e.source,e.target)){
					tmp.add(e);
				}
			}
			boolean connexe = false;
			for(int i = 0 ; i < pere.length ; i++){
				if ((pere[i] < 0) && connexe){
					System.out.println("L'arbre n'est pas connexe.");
					return null;
				}
				else if(pere[i] < 0){
					connexe = true;
				}
			}
			
		}
		
		
		
		System.out.println("Affichage des aretes de l'ACM");
		for(Edge e : tmp){
			System.out.print(e+" | ");
		}
		return tmp;
	}
	
	public void reset(){
		for(int i = 0 ; i < pere.length ; i++){
			pere[i]=-1;
		}
	}
	
}
